package sudoku.util.game;

import java.util.Iterator;
import java.util.Stack;

import sudoku.data.Header;
import sudoku.data.Node;
import sudoku.data.NodePointer;

public class DLX {

  volatile GenerateNewGame game;
  /**
   * an array of Header objects
   */
  protected Header[] columns;
  /**
   * an array of NodePointer objects
   */
  protected NodePointer[] rows;
  protected Stack<Node> sol;
  protected Header h;
  protected int totSolutions;
  public int[][] solution;
  public int[][] savedSolution;
  public int[][] firstSolution;
  public int[][] secondSolution;
  public boolean gotSolution;
  public boolean unique;

  public DLX() {
    this.h = new Header(0);
    this.sol = new Stack<Node>();
    this.totSolutions = 0;
    unique = false;
  }

  /**
   * Prints a solution. This method can be overridden
   */
  public void PrintSolution() {
    if (sol.size() == 0) {
      return;
    }
    Iterator<Node> ien = sol.iterator();
    while (ien.hasNext()) {
    }
  }

  /**
   * Builds the rows and columns arrays. This method mustn't be called if
   * LoadInputFile is called
   * 
   * @param r
   *          number of rows
   * @param c
   *          number of columns
   */
  public void BuildSkeleton(int r, int c) {
    columns = new Header[c];
    rows = new NodePointer[r];
    // columns
    for (int i = 0; i < c; i++) {
      columns[i] = new Header(i);
      columns[i].left = h.left;
      columns[i].right = h;
      h.left.right = columns[i];
      h.left = columns[i];
    }

    // rows
    for (int i = 0; i < r; i++) {
      rows[i] = new NodePointer();
    }
  }

  /**
   * @param r
   *          the string representation of the row (e.g. 01010100011)
   * @param row
   *          the number of the row
   */
  public void AppendRow(String r, int row) {
    if (r.length() > columns.length || row >= rows.length) {
      throw new IndexOutOfBoundsException("Position of nodes longer than the columns header");
    }
    if (r.length() == 0) {
      throw new IllegalArgumentException("Array pos can't be empty");
    }
    Node first = null;
    Node t = null;

    for (int i = 0; i < r.length(); i++) {
      if (r.charAt(i) == '1') {
        if (first != null) {
          t = new Node(row);
          // left - right
          t.left = first.left;
          t.right = first;
          first.left.right = t;
          first.left = t;

          // up - down
          t.down = columns[i];
          t.up = columns[i].up;
          columns[i].up.down = t;
          columns[i].up = t;
          // head
          t.head = columns[i];
          t.head.size++;
        }
        else {
          first = new Node(row);
          first.head = columns[i];
          first.head.size++;
          first.down = columns[i];
          first.up = columns[i].up;
          columns[i].up.down = first;
          columns[i].up = first;
          // pointer
          rows[row].n = first;
        }
      }
    }
  }

  // / <summary>
  // / Appends one row to the matrix
  // / </summary>
  // / <param name="pos">Array filled with the positions of the columns where to
  // append the nodes</param>
  // / <param name="row">The number of the row</param>
  public void AppendRow(int[] pos, int row) {
    if (pos[pos.length - 1] >= columns.length || row >= rows.length) {
      throw new IndexOutOfBoundsException("Position of nodes longer than the columns header");
    }
    if (pos.length == 0) {
      throw new IllegalArgumentException("Array pos can't be empty");
    }

    Node first = new Node(row);
    first.head = columns[pos[0]];
    first.head.size++;
    first.down = columns[pos[0]];
    first.up = columns[pos[0]].up;
    columns[pos[0]].up.down = first;
    columns[pos[0]].up = first;
    rows[row].n = first;
    for (int i = 1; i < pos.length; i++) {
      Node t = new Node(row);
      // left - right
      t.left = first.left;
      t.right = first;
      first.left.right = t;
      first.left = t;

      // up - down
      t.down = columns[pos[i]];
      t.up = columns[pos[i]].up;
      columns[pos[i]].up.down = t;
      columns[pos[i]].up = t;
      // head
      t.head = columns[pos[i]];
      t.head.size++;
    }
  }

  // #endregion

  // #region Selection Methods

  // / <summary>
  // / Finds the minimum sized header in order to minimize the branches for the
  // solution tree
  // / </summary>
  // / <returns>The minimum sized header</returns>
  protected Header FindMin() {
    int min = Integer.MAX_VALUE;
    Header ret = null;
    Header j = (Header) h.right;
    while (j != h) {
      if (j.size < min) {
        min = j.size;
        ret = j;
      }
      j = (Header) j.right;
    }
    return ret;
  }

  // / <summary>
  // / Covers one column (with Knuth DLX cover method) given the header
  // / </summary>
  // / <param name="c">The column to cover</param>
  protected void CoverColumn(Header c) {
    // header unplugging
    c.left.right = c.right;
    c.right.left = c.left;

    // nodes unplugging
    Node i = c.down;
    Node j = null;
    while (i != c) {
      j = i.right;
      while (j != i) {
        j.up.down = j.down;
        j.down.up = j.up;
        j.head.size--;
        j = j.right;
      }
      i = i.down;
    }
  }

  // / <summary>
  // / Covers one column (with Knuth DLX cover method) given the index
  // / </summary>
  // / <param name="index">The index in columns[] for the column to
  // cover</param>
  protected void CoverColumn(int index) {
    CoverColumn(columns[index]);
  }

  // / <summary>
  // / Uncovers one column (with Knuth DLX cover method) given the header
  // / </summary>
  // / <param name="c">The column to uncover</param>
  protected void UncoverColumn(Header c) {
    // nodes plugging
    Node i = c.up;
    Node j = null;
    while (i != c) {
      j = i.left;
      while (j != i) {
        j.up.down = j;
        j.down.up = j;
        j.head.size++;
        j = j.left;
      }
      i = i.up;
    }

    // header plugging
    c.left.right = c;
    c.right.left = c;
  }

  // / <summary>
  // / Uncover one column (with Knuth DLX cover method) given the index
  // / </summary>
  // / <param name="index">The index in columns[] of the column to
  // uncover</param>
  protected void UncoverColumn(int index) {
    UncoverColumn(columns[index]);
  }

  // / <summary>
  // / Selects one row to force solution
  // / </summary>
  // / <param name="index">The index in rows[] of the row to select</param>
  public void SelectRow(int index) {
    Node n = rows[index].n;
    sol.push(n);
    do {
      CoverColumn(n.head);
      n = n.right;
    } while (n != rows[index].n);
  }

  // / <summary>
  // / Unselects the last row pushed in the sol stack
  // / </summary>
  public void UnselectRow() {
    Node n = (sol.pop()).left;
    do {
      UncoverColumn(n.head);
      n = n.left;
    } while (n != rows[n.row].n);
    UncoverColumn(n.head);
  }

  // / <summary>
  // / Selects multiple rows
  // / </summary>
  // / <param name="index">Indexes in rows[] of the rows to select</param>
  public void SelectMultipleRows(int[] index) {
    for (int i = 0; i < index.length; i++) {
      SelectRow(index[i]);
    }
  }

  // / <summary>
  // / Unselects all rows pushed in stack
  // / </summary>
  public void UnselectAllRows() {
    while (sol.size() > 0) {
      UnselectRow();
    }
  }

  public void saveSolution(int i) {

  }

  // #endregion

  // #region Solving algorithm

  // / <summary>
  // / Calls the SolveRecurse method (this can be modified e.g. to work with
  // threads)
  // / </summary>
  public void Solve() {
    sol.clear();
    totSolutions = 0;
    SolveRecurse();
    UnselectAllRows();
  }

  // / <summary>
  // / The original Knuth DLX algorithm
  // / </summary>
  protected void SolveRecurse() {
    if (h.right == h) {
      totSolutions++;
      if (totSolutions == 1) {
        unique = true;
      }
      else {
        unique = false;
      }
      return;
    }
    Header c = FindMin();

    if (c.size == 0) {
      return; // not a good solution
    }

    CoverColumn(c);
    Node r = c.down;
    Node j = null;
    while (r != c) {
      sol.push(r);
      j = r.right;
      while (j != r) {
        CoverColumn(j.head);
        j = j.right;
      }
      SolveRecurse();
      r = sol.pop();
      c = r.head;
      j = r.left;
      while (j != r) {
        UncoverColumn(j.head);
        j = j.left;
      }
      r = r.down;
    }
    UncoverColumn(c);
  }

  // / <summary>
  // / The Knuth DLX algorithm with solution Printing
  // / </summary>
  protected void SolveRecurseAndPrint() {
    if (h.right == h) {
      totSolutions++;
      if (totSolutions == 1) {
        unique = true;
      }
      else {
        unique = false;
      }
      PrintSolution();
      return;
    }
    Header c = FindMin();

    if (c.size == 0) {
      return; // not a good solution
    }

    CoverColumn(c);
    Node r = c.down;
    Node j = null;
    while (r != c) {
      sol.push(r);
      j = r.right;
      while (j != r) {
        CoverColumn(j.head);
        j = j.right;
      }
      SolveRecurseAndPrint();
      r = sol.pop();
      c = r.head;
      j = r.left;
      while (j != r) {
        UncoverColumn(j.head);
        j = j.left;
      }
      r = r.down;
    }
    UncoverColumn(c);
  }

  // / <summary>
  // / The Knuth DLX algorithm with stopping possibility
  // / </summary>
  // / <param name="stopAt">The number of solution to find before
  // stopping</param>
  // / <param name="dim">The dimension of the solution matrix</param>
  protected void SolveRecurseAndStop(int stopAt, int dim) {
    if (gotSolution) {
      return;
    }
    if (h.right == h) {
      solution = new int[dim][dim];
      savedSolution = new int[dim][dim];
      int val;
      int row;
      int col;
      // I have a solution, i put it in solution[,] before stack is popped by
      // returns
      Iterator<Node> ien = sol.iterator();
      while (ien.hasNext()) {
        row = (ien.next()).row;
        val = row % dim;
        col = ((row - val) / dim) % dim;
        solution[row / (dim * dim)][col] = val + 1;
      }
      totSolutions++;
      if (totSolutions == 1) {
        unique = true;
        saveSolution(1);
      }
      else {
        unique = false;
        saveSolution(2);
      }
      if (totSolutions == stopAt) {
        gotSolution = true;
      }
      return;
    }
    Header c = FindMin();

    if (c.size == 0) {
      return; // not a good solution
    }

    CoverColumn(c);
    Node r = c.down;
    Node j = null;
    while (r != c) {
      sol.push(r);
      j = r.right;
      while (j != r) {
        CoverColumn(j.head);
        j = j.right;
      }
      SolveRecurseAndStop(stopAt, dim);
      r = sol.pop();
      c = r.head;
      j = r.left;
      while (j != r) {
        UncoverColumn(j.head);
        j = j.left;
      }
      r = r.down;
    }
    UncoverColumn(c);
  }

  // #endregion

}
